#include <iostream>
#include <queue>

using namespace std;


template <typename T>
void MergeSort(T arr[], int start, int end){
	if(start == end)
		return;

	int mid = (end + start) / 2;
	MergeSort(arr, start, mid);
	MergeSort(arr, mid + 1, end);
	Merge(arr, start, mid, end);
}

template <typename T>
void Merge(T arr[], int start, int mid, int end){
	int first = start, second = mid + 1;
	queue<T> q;
	while(first <= mid && second <= end){
		if(arr[first] < arr[second])
			q.push(arr[first++]);
		else
			q.push(arr[second++]);
	}
	while(first <= mid)
		q.push(arr[first++]);
	while(second <= end)
		q.push(arr[second++]);
	first = 0;
	while(!q.empty()){
		arr[first ++ + start] = q.front();
		q.pop();
	}
}

template <typename T>
T* Merge(T arrA[], T arrB[], size_t sizeA, size_t sizeB){
	T *result = new T[sizeA + sizeB];
	int index = 0, i = 0, j = 0;
	while(i < sizeA && j < sizeB){
		if(arrA[i] <= arrB[j])
			result[index ++] = arrA[i++];
		else
			result[index ++] = arrB[j++];
	}
	while(i < sizeA)
		result[index ++] = arrA[i++];
	while(j < sizeB)
		result[index ++] = arrB[j++];

	return result;
}

void testMergeSort(){
	int arr[] = {3, 2, 5, 6, 9, 1};

	MergeSort<int>(arr, 0, 5);
		
	int index = 0;
	while(index < 6)
		cout << arr[index ++] << endl;
	// getchar();
	int a[] = {1, 3, 5, 7};
	int b[] = {0, 2, 4, 6, 8, 10};

	int *c = Merge<int>(a, b, 4, 6);
	index = 0;
	while(index < 10)
		cout << c[index ++] << endl;
	getchar();
}